В данном задании вам необходимо самостоятельно реализовать один из алгоритмов кластеризации.
По аналогии с классами в scikit-learn, нужно реализовать класс, наследуемый от Base Estimator.
Подробнее про реализацию своих моделей в scikit-learn: here.
В классе помимо __init__() нужно реализовать два метода:
fit() - метод, выполняющий кластеризацию данных.predict() - метод, определяющий для нового объекта, к какому из кластеров он относится. Для удобства можно создавать дополнительные методы класса, которые будут вызываться в fit() или predict().
Функции для вычисления расстояний между объектами самим реализовывать не нужно, используйте реализации из scipy.
from sklearn.base import BaseEstimator, ClusterMixin
from typing import Callable, Union
import numpy as np
from scipy.spatial import distance
from sklearn.base import BaseEstimator, ClusterMixin
from sklearn.datasets import load_iris
class MyDBSCAN(BaseEstimator, ClusterMixin):
"""
My implementation of clustering algorithm
"""
metric: Union[str, Callable]
metric_params: dict
eps: Union[int, float]
min_samples: int
core_sample_coords_: set
labels_: np.array
data: np.array
neighbours: dict
cluster_storage: list
def __init__(
self,
metric="euclidean",
eps=1,
min_samples=3,
metric_params={}
):
self.metric = metric
self.metric_params = metric_params
self.eps = eps
self.min_samples = min_samples
def fit(self, data):
"""
Use data matrix X to compute model parameters
"""
self.data = data
self.neighbours = self._get_neighbours(self.data)
self.core_sample_coords_ = set()
self.labels_ = np.full(len(self.data), -1, dtype=np.int8)
cluster_storage = []
for point in self.neighbours:
if point in self.core_sample_coords_:
continue
if len(self.neighbours[point]) >= self.min_samples:
self.core_sample_coords_.add(point)
new_cluster = self._create_cluster(point, self.neighbours[point])
cluster_storage.append(new_cluster)
for cluster_num, cluster in enumerate(cluster_storage):
for point in cluster:
self.labels_[point] = cluster_num
def predict(self, data):
"""
Using computed model parameters predict cluster
for all objects from matrix X
"""
if self.metric == "precomputed":
raise ValueError("Distance matrix can't be used for prediction.")
labels = np.full(len(data), -1, dtype=np.int8)
neighbours = self._get_neighbours(data)
for idx in neighbours:
if len(neighbours[idx]) > 0:
labels[idx] = self.labels_[neighbours[idx][0]]
return labels
def _get_neighbours(self, other):
distance_matrix = np.array([], dtype=np.float16)
neighbours = {}
if self.metric == "precomputed":
distance_matrix = self.data
elif callable(self.metric) or self.metric in dir(distance):
distance_matrix = distance.cdist(
other,
self.data,
self.metric,
**self.metric_params
)
for idx, row in enumerate(distance_matrix):
neighbours[idx] = np.where(row <= self.eps)[0]
return neighbours
def _create_cluster(self, point, neighbours):
"""
Making new cluster.
"""
cluster = [point]
for neighbour in neighbours:
if neighbour not in self.core_sample_coords_:
if len(self.neighbours[neighbour]) >= self.min_samples:
self.core_sample_coords_.add(neighbour)
expanded_cluster = self._create_cluster(
neighbour,
self.neighbours[neighbour]
)
cluster.extend(expanded_cluster)
else:
cluster.append(neighbour)
return cluster
Алгоритм агломеративной кластеризации.
Параметры:
scipy.spatial.distance, самописные функции (callable) и предрассчитанная матрица расстояний. Атрибуты:
linkage() из scipy.cluster.hierarchy;Дополнительно нужно реализовать метод get_labels() для вычисления labels_, он должен быть аналогичен fcluster().
В случае, если n_clusters не None, то после вычисления матрицы z_ в методе fit() должен быть вызван get_labels() с соответствующими параметрами, и вычислены labels_. В других случаях метод fit() только вычисляет матрицу z_, для вычисления labels_ нужно явно вызывать get_labels().
Метод predict(): Кластер для нового объекта определяется по методу, заданному в linkage.
Note: Метод predict() не выполняется в случае, когда metric - это матрица расстояний.
Алгоритм Dbscan.
Параметры:
scipy.spatial.distance, самописные функции (callable) и предрассчитанная матрица расстояний. Атрибуты:
Метод predict(): Для нового объекта вычисляется число основных точек из каждого кластера, попавших в окрестность $\varepsilon$. Объект определяется в кластер с наибольшим числом таких точек.
Note: Метод predict() не выполняется в случае, когда metric - это матрица расстояний.
Алгоритм K-Means.
Параметры:
Атрибуты:
Метод predict(): Новый объект определяется в кластер, центр которого расположен ближе всех к этому объекту.
Вашу реализацию необходимо сравнить с питоновской реализацией алгоритма из sklearn или scipy. Результаты кластеризации должны совпадать.
Также необходимо сравнить скорость работы вашей реализации и питоновской (это нормально, если ваша реализация будет медленнее).
Сравнение необходимо выполнить на наборе данных iris.
import numpy as np
import pandas as pd
from sklearn.datasets import load_iris
import matplotlib.pyplot as plt
import seaborn as sns
iris = load_iris()
X = iris.data # использовать для кластеризации
y = iris.target # истинные метки цветков
X_iris = pd.DataFrame(X, columns=iris.feature_names)
X_iris['class'] = [iris.target_names[i] for i in y]
sns.pairplot(X_iris, hue='class', plot_kws={'alpha':0.5}, vars=iris.feature_names)
plt.show()
from sklearn.cluster import DBSCAN
dbscan = DBSCAN(eps=1, min_samples=3, metric="euclidean")
dbscan_hm = MyDBSCAN(eps=1, min_samples=3, metric="euclidean")
%%timeit -n200 -r 20
dbscan.fit(X)
dbscan.labels_
200 loops, best of 20: 2.16 ms per loop
%%timeit -n200 -r 20
dbscan_hm.fit(X)
dbscan_hm.labels_
200 loops, best of 20: 2.12 ms per loop
assert all(dbscan.labels_ == dbscan_hm.labels_), "Clustering results are not identical."
from sklearn.metrics import silhouette_score
silhouette_score(dbscan_hm.labels_.reshape(-1, 1), y)
0.3333333333333333
Дополнительно вы можете поработать над эффективностью алгоритма по скорости и памяти, добавить поддержку многопоточности, или расширить базовый функционал.
%load_ext cython
%%cython
from sklearn.base import BaseEstimator, ClusterMixin
from typing import Callable, Union
import numpy as np
from scipy.spatial import distance
from sklearn.base import BaseEstimator, ClusterMixin
from sklearn.datasets import load_iris
from sklearn.cluster import DBSCAN
cimport numpy
cdef dict neighbours
cdef list cluster_storage
cdef int min_samples
class MyDBSCAN(BaseEstimator, ClusterMixin):
"""
My implementation of clustering algorithm
"""
metric: Union[str, Callable]
metric_params: dict
eps: Union[int, float]
core_sample_coords_: set
def __init__(
self,
metric="euclidean",
eps=1,
int min_samples=3,
dict metric_params={}
):
self.metric = metric
self.metric_params = metric_params
self.eps = eps
self.min_samples = min_samples
def fit(self, numpy.ndarray[numpy.float_t, ndim=2] data):
"""
Use data matrix X to compute model parameters
"""
cdef dict neighbours
cdef list cluster_storage
cdef numpy.ndarray[numpy.int_t] labels
self.data = data
self.neighbours = self._get_neighbours(self.data)
self.core_sample_coords_ = set()
labels_ = np.full(len(self.data), -1)
self.labels_ = labels_
cluster_storage = []
for point in self.neighbours:
if point in self.core_sample_coords_:
continue
if len(self.neighbours[point]) >= self.min_samples:
self.core_sample_coords_.add(point)
new_cluster = self._create_cluster(point, self.neighbours[point])
cluster_storage.append(new_cluster)
for cluster_num, cluster in enumerate(cluster_storage):
for point in cluster:
self.labels_[point] = cluster_num
def predict(self, numpy.ndarray[numpy.float_t, ndim=2] arr):
"""
Using computed model parameters predict cluster
for all objects from matrix X
"""
cdef numpy.ndarray[numpy.int_t] labels
if self.metric == "precomputed":
raise ValueError("Distance matrix can't be used for prediction.")
labels = np.full(len(arr), -1)
neighbours = self._get_neighbours(arr)
for idx in neighbours:
if len(neighbours[idx]) > 0:
labels[idx] = self.labels_[neighbours[idx][0]]
return labels
def _get_neighbours(self, numpy.ndarray[numpy.float_t, ndim=2] other):
cdef numpy.ndarray[numpy.float_t, ndim=2] distance_matrix
neighbours = {}
if self.metric == "precomputed":
distance_matrix = self.data
elif callable(self.metric) or self.metric in dir(distance):
distance_matrix = distance.cdist(
other,
self.data,
self.metric,
**self.metric_params
)
for idx, row in enumerate(distance_matrix):
neighbours[idx] = np.where(row <= self.eps)[0]
return neighbours
def _create_cluster(self, numpy.int_t point, neighbours):
"""
Making new cluster.
"""
cluster = [point]
for neighbour in neighbours:
if neighbour not in self.core_sample_coords_:
if len(self.neighbours[neighbour]) >= self.min_samples:
self.core_sample_coords_.add(neighbour)
expanded_cluster = self._create_cluster(
neighbour,
self.neighbours[neighbour]
)
cluster.extend(expanded_cluster)
else:
cluster.append(neighbour)
return cluster
iris = load_iris()
X = iris.data # использовать для кластеризации
dbscan = DBSCAN(eps=1, min_samples=3, metric="euclidean")
dbscan_hm = MyDBSCAN(eps=1, min_samples=3, metric="euclidean")
def db_fit(model):
model.fit(X)
import time
start = time.time()
db_fit(dbscan)
print("Original:", time.time() - start)
start = time.time()
db_fit(dbscan_hm)
print("Handmade:", time.time() - start)
assert all(dbscan.labels_ == dbscan_hm.labels_), "Clustering results are not identical."
Original: 0.0027534961700439453 Handmade: 0.002295970916748047
pd.set_option('display.max_rows', 50)
Vars = pd.read_csv('Vars.txt', sep='\t')
Vars[Vars.iloc[:,2] == 1]
| ФИО | Группа | Вариант № | |
|---|---|---|---|
| 0 | Бакурский Андрей Сергеевич | 1 ИАД | 1 |
| 2 | Бекина Светлана Сергеевна | 1 ИАД | 1 |
| 3 | Бекусов Михаил Александрович | 1 ИАД | 1 |
| 9 | Конина Татьяна Дмитриевна | 1 ИАД | 1 |
| 11 | Лукичева Полина Александровна | 1 ИАД | 1 |
| 12 | Моничева Арина Александровна | 1 ИАД | 1 |
| 22 | Трухин Егор Сергеевич | 1 ИАД | 1 |
| 23 | Шарунов Евгений Александрович | 1 ИАД | 1 |
| 24 | Шатилов Виктор Алексеевич | 1 ИАД | 1 |
| 27 | Астахова Елизавета Евгеньевна | 2 ИАД | 1 |
| 29 | Баранов Денис Алексеевич | 2 ИАД | 1 |
| 30 | Баховаддинов Искандар Худайбердиевич | 2 ИАД | 1 |
| 34 | Казюлина Марина Сергеевна | 2 ИАД | 1 |
| 35 | Карабасова Юлия Алексеевна | 2 ИАД | 1 |
| 38 | Меркулова Екатерина Владимировна | 2 ИАД | 1 |
| 40 | Сазанов Илья Денисович | 2 ИАД | 1 |
| 45 | Тормашова Валерия Сергеевна | 2 ИАД | 1 |
| 47 | Федоров Макар Андреевич | 2 ИАД | 1 |
| 50 | Шешменева Кристина Сергеевна | 2 ИАД | 1 |
| 53 | Артюх Майя Сергеевна | 3 ИАД | 1 |
| 59 | Лашина Надежда Андреевна | 3 ИАД | 1 |
| 61 | Рябинина Полина Викторовна | 3 ИАД | 1 |
| 63 | Харинский Дмитрий Сергеевич | 3 ИАД | 1 |
Vars[Vars.iloc[:,2] == 2]
| ФИО | Группа | Вариант № | |
|---|---|---|---|
| 1 | Балаян Роман Каренович | 1 ИАД | 2 |
| 5 | Даняев Артем Андреевич | 1 ИАД | 2 |
| 7 | Ешманов Павел Андреевич | 1 ИАД | 2 |
| 10 | Костин Андрей Олегович | 1 ИАД | 2 |
| 15 | Ожиганова Полина Максимовна | 1 ИАД | 2 |
| 17 | Сапожников Андрей Михайлович | 1 ИАД | 2 |
| 18 | Семаев Никита Юрьевич | 1 ИАД | 2 |
| 21 | Суворов Артём Андреевич | 1 ИАД | 2 |
| 25 | Южаков Максим Вячеславович | 1 ИАД | 2 |
| 28 | Бабий Александр Сергеевич | 2 ИАД | 2 |
| 32 | Гаранина Мария Евгеньевна | 2 ИАД | 2 |
| 33 | Гаращенкова Анна Александровна | 2 ИАД | 2 |
| 36 | Корякин Владислав Андреевич | 2 ИАД | 2 |
| 39 | Мушка Никита Андреевич | 2 ИАД | 2 |
| 42 | Соколова Анна Ильинична | 2 ИАД | 2 |
| 43 | Солдаткин Константин Алексеевич | 2 ИАД | 2 |
| 48 | Харханова Екатерина Михайловна | 2 ИАД | 2 |
| 51 | Шувар Алена Олеговна | 2 ИАД | 2 |
| 55 | Дудин Григорий Алексеевич | 3 ИАД | 2 |
| 56 | Егоров Николай Михайлович | 3 ИАД | 2 |
| 58 | Кучеренко Анна Васильевна | 3 ИАД | 2 |
| 60 | Матвеева Дарья Игоревна | 3 ИАД | 2 |
| 64 | Частова Екатерина Робертовна | 3 ИАД | 2 |
| 67 | Шемет Савелий Кириллович | 3 ИАД | 2 |
Vars[Vars.iloc[:,2] == 3]
| ФИО | Группа | Вариант № | |
|---|---|---|---|
| 4 | Боряев Сергей Сергеевич | 1 ИАД | 3 |
| 6 | Дыряев Даниил Александрович | 1 ИАД | 3 |
| 8 | Игумнова Наталья Дмитриевна | 1 ИАД | 3 |
| 13 | Мурзинов Михаил Денисович | 1 ИАД | 3 |
| 14 | Николаева Олеся Игоревна | 1 ИАД | 3 |
| 16 | Османов Ислам Рамилевич | 1 ИАД | 3 |
| 19 | Смирнов Григорий Андреевич | 1 ИАД | 3 |
| 20 | Стифеев Никита Владимирович | 1 ИАД | 3 |
| 26 | Арбузова Екатерина Михайловна | 2 ИАД | 3 |
| 31 | Варгин Дмитрий Александрович | 2 ИАД | 3 |
| 37 | Левин Глеб Сергеевич | 2 ИАД | 3 |
| 41 | Смирнов Дмитрий Викторович | 2 ИАД | 3 |
| 44 | Терентьева Анастасия Олеговна | 2 ИАД | 3 |
| 46 | Точкова Арина Андреевна | 2 ИАД | 3 |
| 49 | Шарапов Максим Сергеевич | 2 ИАД | 3 |
| 52 | Юдакова Олеся Валерьевна | 2 ИАД | 3 |
| 54 | Басыров Андрей Дмитриевич | 3 ИАД | 3 |
| 57 | Закареишвили Гиоргий Годердзиевич | 3 ИАД | 3 |
| 62 | Семенова Елена Андреевна | 3 ИАД | 3 |
| 65 | Чернов Роман Александрович | 3 ИАД | 3 |
| 66 | Шауклис Александр Николаевич | 3 ИАД | 3 |
from sklearn.preprocessing import StandardScaler
import numpy as np
import pandas as pd
from matplotlib import pyplot as plt
from scipy.cluster.hierarchy import dendrogram
from sklearn.cluster import AgglomerativeClustering, KMeans, DBSCAN
import scipy.cluster.hierarchy as sch
from sklearn.manifold import TSNE
import seaborn as sns
from sklearn.neighbors import kneighbors_graph
from scipy.spatial import distance
В данном задании вам предлагается проанализировать набор данных по различным городам США. Каждый город характеризуется следующими признаками:
pd.set_option('display.max_colwidth', None)
data_desc = pd.read_csv('Data_Description.txt', sep=':')
data_desc
| Attribute | Description | |
|---|---|---|
| 0 | Place | City, state (postal code) |
| 1 | Climate & Terrain | Very hot and very cold months, seasonal temperature variation, heating- and cooling-degree days, freezing days, zero-degree days, ninety-degree days. |
| 2 | Housing | Utility bills, property taxes, mortgage payments. |
| 3 | Health Care & Environment | Per capita physicians, teaching hospitals, medical schools, cardiac rehabilitation centers, comprehensive cancer treatment centers, hospices, insurance/hospitalization costs index, flouridation of drinking water, air pollution. |
| 4 | Crime | Violent crime rate, property crime rate. |
| 5 | Transportation | Daily commute, public transportation, Interstate highways, air service, passenger rail service. |
| 6 | Education | Pupil/teacher ratio in the public K-12 system, effort index in K-12, accademic options in higher education. |
| 7 | The Arts | Museums, fine arts and public radio stations, public television stations, universities offering a degree or degrees in the arts, symphony orchestras, theatres, opera companies, dance companies, public libraries. |
| 8 | Recreation | Good restaurants, public golf courses, certified lanes for tenpin bowling, movie theatres, zoos, aquariums, family theme parks, sanctioned automobile race tracks, pari-mutuel betting attractions, major- and minor- league professional sports teams, NCAA Division I football and basketball teams, miles of ocean or Great Lakes coastline, inland water, national forests, national parks, or national wildlife refuges, Consolidated Metropolitan Statistical Area access. |
| 9 | Economics | Average household income adjusted for taxes and living costs, income growth, job growth. |
| 10 | Longitude | Longitude |
| 11 | Latitude | Latitude |
| 12 | Population | Population |
Housing и Crime - наоборот.Population- статистический признак, не имеющий интерпретации как “лучше-хуже”.Place - уникальный идентификатор объекта (города), он не должен использоваться при кластеризации.Longitude и Latitude. Их также не следует использовать при кластеризации данных.data = pd.read_csv('Data.txt', sep=' ')
data
| Place | Climate | HousingCost | HlthCare | Crime | Transp | Educ | Arts | Recreat | Econ | Long | Lat | Pop | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | Abilene,TX | 521 | 6200 | 237 | 923 | 4031 | 2757 | 996 | 1405 | 7633 | -99.6890 | 32.5590 | 110932 |
| 1 | Akron,OH | 575 | 8138 | 1656 | 886 | 4883 | 2438 | 5564 | 2632 | 4350 | -81.5180 | 41.0850 | 660328 |
| 2 | Albany,GA | 468 | 7339 | 618 | 970 | 2531 | 2560 | 237 | 859 | 5250 | -84.1580 | 31.5750 | 112402 |
| 3 | Albany-Schenectady-Troy,NY | 476 | 7908 | 1431 | 610 | 6883 | 3399 | 4655 | 1617 | 5864 | -73.7983 | 42.7327 | 835880 |
| 4 | Albuquerque,NM | 659 | 8393 | 1853 | 1483 | 6558 | 3026 | 4496 | 2612 | 5727 | -106.6500 | 35.0830 | 419700 |
| ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... |
| 324 | Worcester,MA | 562 | 8715 | 1805 | 680 | 3643 | 3299 | 1784 | 910 | 5040 | -71.7950 | 42.2720 | 402918 |
| 325 | Yakima,WA | 535 | 6440 | 317 | 1106 | 3731 | 2491 | 996 | 2140 | 4986 | -120.5130 | 46.5950 | 172508 |
| 326 | York,PA | 540 | 8371 | 713 | 440 | 2267 | 2903 | 1022 | 842 | 4946 | -76.7280 | 39.9600 | 381255 |
| 327 | Youngstown-Warren,OH | 570 | 7021 | 1097 | 938 | 3374 | 2920 | 2797 | 1327 | 3894 | -80.7290 | 41.1700 | 531350 |
| 328 | Yuba-City,CA | 608 | 7875 | 212 | 1179 | 2768 | 2387 | 122 | 918 | 4694 | -121.6220 | 39.1280 | 101979 |
329 rows × 13 columns
Place, Long и Lat. from sklearn import metrics
processed_data = data.drop(["Place", "Long", "Lat"], axis=1)
processed_data.head()
| Climate | HousingCost | HlthCare | Crime | Transp | Educ | Arts | Recreat | Econ | Pop | |
|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 521 | 6200 | 237 | 923 | 4031 | 2757 | 996 | 1405 | 7633 | 110932 |
| 1 | 575 | 8138 | 1656 | 886 | 4883 | 2438 | 5564 | 2632 | 4350 | 660328 |
| 2 | 468 | 7339 | 618 | 970 | 2531 | 2560 | 237 | 859 | 5250 | 112402 |
| 3 | 476 | 7908 | 1431 | 610 | 6883 | 3399 | 4655 | 1617 | 5864 | 835880 |
| 4 | 659 | 8393 | 1853 | 1483 | 6558 | 3026 | 4496 | 2612 | 5727 | 419700 |
scaler = StandardScaler()
scaled_data = pd.DataFrame(scaler.fit_transform(processed_data), columns=processed_data.columns)
scaled_data.head()
| Climate | HousingCost | HlthCare | Crime | Transp | Educ | Arts | Recreat | Econ | Pop | |
|---|---|---|---|---|---|---|---|---|---|---|
| 0 | -0.147006 | -0.901297 | -0.947340 | -0.106712 | -0.123592 | -0.180726 | -0.464893 | -0.546646 | 1.946433 | -0.460990 |
| 1 | 0.300664 | -0.087570 | 0.469568 | -0.210467 | 0.464411 | -1.176652 | 0.520604 | 0.974442 | -1.085467 | 0.154950 |
| 2 | -0.586386 | -0.423054 | -0.566902 | 0.025084 | -1.158809 | -0.795765 | -0.628640 | -1.223512 | -0.254304 | -0.459342 |
| 3 | -0.520064 | -0.184142 | 0.244900 | -0.984419 | 1.844699 | 1.823613 | 0.324497 | -0.283834 | 0.312735 | 0.351765 |
| 4 | 0.997040 | 0.019500 | 0.666278 | 1.463626 | 1.620402 | 0.659098 | 0.290194 | 0.949648 | 0.186213 | -0.114824 |
def count_cluster_samples(labels):
unique, counts = np.unique(clusters, return_counts=True)
print(dict(zip(unique, counts)))
def plot_samples(data, clusters=None):
if clusters is not None:
return sns.scatterplot(
x=data[:, 0],
y=data[:, 1],
c=clusters,
cmap="rainbow"
)
else:
return sns.scatterplot(
x=data[:, 0],
y=data[:, 1],
)
from collections import namedtuple
def compute_metrics(X, labels):
silhouette = metrics.silhouette_score(X, labels)
davies = metrics.davies_bouldin_score(X, labels)
calinski = metrics.calinski_harabasz_score(X, labels)
print(f"Silhouette: {silhouette}")
print(f"Davies-Bouldin: {davies}")
print(f"Calinski-Harabasz: {calinski}")
Metrics = namedtuple("Metrics", ["silhouette", "davies", "calinski"])
return Metrics(silhouette, davies, calinski)
plt.figure(figsize=(10, 7))
plt.title("City Dendrograms")
dend = sch.dendrogram(sch.linkage(scaled_data, method='ward'))
data_embedded = TSNE(n_components=2).fit_transform(scaled_data.values)
plot_samples(data_embedded)
# NB! Размерность снижена достаточно сильно,
# поэтому визуализация может быть не совсем репрезентативна
<AxesSubplot:>
metric_stats = {}
ward & euclidean distances¶knn_graph = kneighbors_graph(scaled_data, 30, include_self=False)
clusters = AgglomerativeClustering(
n_clusters=3,
linkage="ward",
affinity="euclidean"
).fit_predict(scaled_data)
count_cluster_samples(clusters)
plot_samples(data_embedded, clusters=clusters)
{0: 142, 1: 181, 2: 6}
<matplotlib.axes._subplots.AxesSubplot at 0x7f1ead7f6fd0>
metric_stats["agglomerative_ward"] = compute_metrics(scaled_data, clusters)
Silhouette: 0.1740790530715999 Davies-Bouldin: 1.6386724367395287 Calinski-Harabasz: 72.21532753341644
clusters = AgglomerativeClustering(
n_clusters=3,
linkage="ward",
affinity="euclidean",
connectivity=knn_graph
).fit_predict(scaled_data)
count_cluster_samples(clusters)
plot_samples(data_embedded, clusters=clusters)
{0: 142, 1: 181, 2: 6}
<matplotlib.axes._subplots.AxesSubplot at 0x7f1ead7e1050>
# 3rd cluster samples
processed_data.iloc[np.where(clusters == 2)[0], :]
| Climate | HousingCost | HlthCare | Crime | Transp | Educ | Arts | Recreat | Econ | Pop | |
|---|---|---|---|---|---|---|---|---|---|---|
| 42 | 623 | 11609 | 5301 | 1215 | 6801 | 3479 | 21042 | 3066 | 6363 | 2805911 |
| 64 | 514 | 10913 | 5766 | 1034 | 7742 | 3486 | 24846 | 2856 | 5205 | 6060387 |
| 178 | 885 | 13868 | 5153 | 1960 | 4345 | 3195 | 23567 | 3948 | 5316 | 7477503 |
| 212 | 638 | 13358 | 7850 | 2498 | 8625 | 2984 | 56745 | 3579 | 5338 | 8274961 |
| 233 | 630 | 8310 | 5158 | 1059 | 5903 | 3781 | 17270 | 1979 | 5638 | 4716818 |
| 313 | 631 | 13724 | 4361 | 1317 | 8236 | 3635 | 21701 | 1578 | 6072 | 3250822 |
clusters = AgglomerativeClustering(
n_clusters=2,
linkage="ward",
affinity="euclidean",
connectivity=knn_graph
).fit_predict(scaled_data)
count_cluster_samples(clusters)
plot_samples(data_embedded, clusters=clusters)
{0: 148, 1: 181}
<matplotlib.axes._subplots.AxesSubplot at 0x7f1eac4e8890>
clusters = AgglomerativeClustering(
n_clusters=2,
linkage="ward",
affinity="euclidean"
).fit_predict(scaled_data)
count_cluster_samples(clusters)
plot_samples(data_embedded, clusters=clusters)
{0: 148, 1: 181}
<matplotlib.axes._subplots.AxesSubplot at 0x7f1eac611cd0>
knn графа с 30 соседями идентичны результатам без использования knn графа для ward & euclideanward & euclidean представлен только 6 наблюдениями, что похоже на данные из дендрограммы (там ведь тоже использован ward)complete linkage¶# Manhattan is equal to L1 and Euclidean is equal to L2
# Thus, we'll use only Manhattan and Euclidean
# for efficiency and readability purposes
fig, axes = plt.subplots(ncols=6, figsize=(35, 5))
for idx, metric in enumerate(
{
"euclidean",
"cosine",
"manhattan",
"minkowski",
"chebyshev",
"canberra"
}
):
clusters = AgglomerativeClustering(
n_clusters=3,
linkage="complete",
affinity=metric
).fit_predict(scaled_data)
axes[idx].set_xlabel(metric)
axes[idx].scatter(x=data_embedded[:, 0], y=data_embedded[:, 1], c=clusters, cmap="rainbow")
clusters = AgglomerativeClustering(
n_clusters=3,
linkage="complete",
affinity="cosine"
).fit_predict(scaled_data)
metric_stats["agglomerative_complete_cosine"] = compute_metrics(scaled_data, clusters)
Silhouette: 0.13931449234623647 Davies-Bouldin: 2.339718960788736 Calinski-Harabasz: 43.342180410474114
single linkage¶fig, axes = plt.subplots(ncols=6, figsize=(35, 5))
for idx, metric in enumerate(
{
"euclidean",
"cosine",
"manhattan",
"minkowski",
"chebyshev",
"canberra"
}
):
clusters = AgglomerativeClustering(
n_clusters=3,
linkage="single",
affinity=metric
).fit_predict(scaled_data)
axes[idx].set_xlabel(metric)
axes[idx].scatter(x=data_embedded[:, 0], y=data_embedded[:, 1], c=clusters, cmap="rainbow")
average linkage¶fig, axes = plt.subplots(ncols=6, figsize=(35, 5))
for idx, metric in enumerate(
{
"euclidean",
"cosine",
"manhattan",
"minkowski",
"chebyshev",
"canberra"
}
):
clusters = AgglomerativeClustering(
n_clusters=3,
linkage="average",
affinity=metric
).fit_predict(scaled_data)
axes[idx].set_xlabel(metric)
axes[idx].scatter(x=data_embedded[:, 0], y=data_embedded[:, 1], c=clusters, cmap="rainbow")
clusters = AgglomerativeClustering(
n_clusters=3,
linkage="average",
affinity="cosine"
).fit_predict(scaled_data)
metric_stats["agglomerative_average_cosine"] = compute_metrics(scaled_data, clusters)
Silhouette: 0.08797497634337614 Davies-Bouldin: 2.0850910072225193 Calinski-Harabasz: 53.813409016452525
Выводы:
single linkage) достаточно бесполезно для этого датасетаaverage & canberra при 3х кластерах выделяет буквально один сэмпл для одного из кластеров, хотя с остальным он справился достаточно неплохоcomplete & cosine и average & cosine и canberra в связке complete & canberra.Расстояния, которые могут быть использованы для кластеризации этого датасета:
ward & euclidean хорошо разбивает данные на кластеры, но 3й выделенный кластер может быть интерпретирован как выбросыcomplete & cosine и average & cosine тоже могут быть использованы для кластеризации, но стоит учитывать, что косинусное расстояние не учитывает абсолютное расстояние между наблюдениями в векторном пространстве, а только угол между ними, что позволяет выявлять тенденции в данных. Вывод по используемым расстояниям:
# Heuristics for euclidean distance
from sklearn.neighbors import NearestNeighbors
nearest_neighbors = NearestNeighbors(n_neighbors=11, metric="euclidean")
neighbors = nearest_neighbors.fit(scaled_data)
distances, indices = neighbors.kneighbors(scaled_data)
distances = np.sort(distances[:,10], axis=0)
fig = plt.figure(figsize=(5, 5))
plt.plot(distances)
plt.xlabel("Points")
plt.ylabel("Distance")
Text(0, 0.5, 'Distance')
# Using optimal eps from the plot
fig, axes = plt.subplots(ncols=7, figsize=(30, 4))
for idx, i in enumerate(range(3, 10)):
dbscan = DBSCAN(metric="euclidean", eps=3.7, min_samples=i)
clusters = dbscan.fit_predict(scaled_data)
axes[idx].set_xlabel(f"min {i} samples")
axes[idx].scatter(x=data_embedded[:, 0], y=data_embedded[:, 1], c=clusters, cmap="rainbow")
dbscan = DBSCAN(metric="euclidean", eps=3.7, min_samples=6)
clusters = dbscan.fit_predict(scaled_data)
metric_stats["dbscan_euclidean"] = compute_metrics(scaled_data, clusters)
Silhouette: 0.6129352430409912 Davies-Bouldin: 0.8082913537210814 Calinski-Harabasz: 66.79375705838629
# Using hand-picked eps
fig, axes = plt.subplots(ncols=7, figsize=(30, 4))
for idx, i in enumerate(range(3, 10)):
dbscan = DBSCAN(metric="euclidean", eps=1.3, min_samples=i)
clusters = dbscan.fit_predict(scaled_data)
axes[idx].set_xlabel(f"min {i} samples")
axes[idx].scatter(x=data_embedded[:, 0], y=data_embedded[:, 1], c=clusters, cmap="rainbow")
# Heuristics for cosine distance
from sklearn.neighbors import NearestNeighbors
nearest_neighbors = NearestNeighbors(n_neighbors=11, metric="cosine")
neighbors = nearest_neighbors.fit(scaled_data)
distances, indices = neighbors.kneighbors(scaled_data)
distances = np.sort(distances[:,10], axis=0)
fig = plt.figure(figsize=(5, 5))
plt.plot(distances)
plt.xlabel("Points")
plt.ylabel("Distance")
Text(0, 0.5, 'Distance')
# Using eps from the plot
fig, axes = plt.subplots(ncols=7, figsize=(30, 4))
for idx, i in enumerate(range(3, 10)):
dbscan = DBSCAN(metric="cosine", eps=0.36, min_samples=i)
clusters = dbscan.fit_predict(scaled_data)
axes[idx].set_xlabel(f"min {i} samples")
axes[idx].scatter(
x=data_embedded[:, 0],
y=data_embedded[:, 1],
c=clusters,
cmap="rainbow"
)
# Using hand-picked eps
fig, axes = plt.subplots(ncols=7, figsize=(30, 4))
for idx, i in enumerate(range(3, 10)):
dbscan = DBSCAN(metric="cosine", eps=0.16, min_samples=i)
clusters = dbscan.fit_predict(scaled_data)
axes[idx].set_xlabel(f"min {i} samples")
axes[idx].scatter(
x=data_embedded[:, 0],
y=data_embedded[:, 1],
c=clusters,
cmap="rainbow"
)
dbscan = DBSCAN(metric="cosine", eps=0.16, min_samples=9)
clusters = dbscan.fit_predict(scaled_data)
metric_stats["dbscan_cosine"] = compute_metrics(scaled_data, clusters)
Silhouette: 0.08862792526465896 Davies-Bouldin: 1.7962841929950921 Calinski-Harabasz: 59.72216013322556
# Heuristics for canberra distance
from sklearn.neighbors import NearestNeighbors
nearest_neighbors = NearestNeighbors(n_neighbors=11, metric="canberra")
neighbors = nearest_neighbors.fit(scaled_data)
distances, indices = neighbors.kneighbors(scaled_data)
distances = np.sort(distances[:,10], axis=0)
fig = plt.figure(figsize=(5, 5))
plt.plot(distances)
plt.xlabel("Points")
plt.ylabel("Distance")
Text(0, 0.5, 'Distance')
# Using eps from the plot
fig, axes = plt.subplots(ncols=7, figsize=(30, 4))
for idx, i in enumerate(range(3, 10)):
dbscan = DBSCAN(metric="canberra", eps=5.5, min_samples=i)
clusters = dbscan.fit_predict(scaled_data)
axes[idx].set_xlabel(f"min {i} samples")
axes[idx].scatter(
x=data_embedded[:, 0],
y=data_embedded[:, 1],
c=clusters,
cmap="rainbow"
)
# Using hand-picked eps
fig, axes = plt.subplots(ncols=7, figsize=(30, 4))
for idx, i in enumerate(range(3, 10)):
dbscan = DBSCAN(metric="canberra", eps=4.4, min_samples=i)
clusters = dbscan.fit_predict(scaled_data)
axes[idx].set_xlabel(f"min {i} samples")
axes[idx].scatter(
x=data_embedded[:, 0],
y=data_embedded[:, 1],
c=clusters,
cmap="rainbow"
)
dbscan = DBSCAN(metric="canberra", eps=4.4, min_samples=7)
clusters = dbscan.fit_predict(scaled_data)
metric_stats["dbscan_canberra"] = compute_metrics(scaled_data, clusters)
Silhouette: 0.06696330466267836 Davies-Bouldin: 2.742753086381493 Calinski-Harabasz: 43.64947485308241
cosine и canberra на графике даже нет чёткого места изгиба для выбора epseps=0.16 & cosine & min_samples ∈ {7,8,9}, eps=1.3 & euclidean & min_samples ∈ {5,6,9}и eps=4.4 & canberra & min_samples=7wss = []
n_clusters = range(1,15)
for k in n_clusters:
km = KMeans(n_clusters=k)
km = km.fit(scaled_data.values)
wss.append(km.inertia_)
plt.plot(n_clusters, wss, 'bx-')
plt.xlabel('k')
plt.ylabel('Sum_of_squared_distances')
plt.title('Elbow Method For Optimal k')
plt.show()
km = KMeans(n_clusters=3)
clusters = km.fit_predict(scaled_data.values)
plot_samples(data_embedded, clusters)
<matplotlib.axes._subplots.AxesSubplot at 0x7f1eaa830610>
km = KMeans(n_clusters=3)
clusters = km.fit_predict(scaled_data.values)
metric_stats["kmeans"] = compute_metrics(scaled_data, clusters)
Silhouette: 0.2378531239217623 Davies-Bouldin: 1.5285566112731594 Calinski-Harabasz: 86.09157814257729
!pip install hdbscan --quiet
|████████████████████████████████| 6.4MB 1.9MB/s
Installing build dependencies ... done
Getting requirements to build wheel ... done
Preparing wheel metadata ... done
Building wheel for hdbscan (PEP 517) ... done
from hdbscan import HDBSCAN
# choosing optimal min_cluster_size
fig, axes = plt.subplots(ncols=8, figsize=(35, 3))
for idx, i in enumerate(range(3, 11)):
hdbscan = HDBSCAN(metric="euclidean", min_cluster_size=i)
clusters = hdbscan.fit(scaled_data)
axes[idx].set_xlabel(f"min cluster size - {i}")
axes[idx].scatter(
x=data_embedded[:, 0],
y=data_embedded[:, 1],
c=clusters.labels_,
cmap="rainbow"
)
# choosing optimal min_samples and epsilon
fig, axes = plt.subplots(ncols=8, figsize=(35, 3))
for idx, i in enumerate(range(3, 11)):
hdbscan = HDBSCAN(
metric="euclidean",
min_cluster_size=4,
min_samples=i,
cluster_selection_epsilon=3.1
)
clusters = hdbscan.fit(scaled_data)
axes[idx].set_xlabel(f"min {i} samples")
axes[idx].scatter(
x=data_embedded[:, 0],
y=data_embedded[:, 1],
c=clusters.labels_,
cmap="rainbow"
)
hdbscan = HDBSCAN(
metric="euclidean",
min_cluster_size=4,
min_samples=3,
cluster_selection_epsilon=3.1
)
clusters = hdbscan.fit(scaled_data)
metric_stats["hdbscan"] = compute_metrics(scaled_data, clusters.labels_)
Silhouette: 0.12551886836376325 Davies-Bouldin: 1.9489708574623812 Calinski-Harabasz: 27.39201136703522
metric_stats
{'agglomerative_average_cosine': Metrics(silhouette=0.08797497634337614, davies=2.0850910072225193, calinski=53.813409016452525),
'agglomerative_complete_cosine': Metrics(silhouette=0.13931449234623647, davies=2.339718960788736, calinski=43.342180410474114),
'agglomerative_ward': Metrics(silhouette=0.1740790530715999, davies=1.6386724367395287, calinski=72.21532753341644),
'dbscan_canberra': Metrics(silhouette=0.06696330466267836, davies=2.742753086381493, calinski=43.64947485308241),
'dbscan_cosine': Metrics(silhouette=0.08862792526465896, davies=1.7962841929950921, calinski=59.72216013322556),
'dbscan_euclidean': Metrics(silhouette=0.6129352430409912, davies=0.8082913537210814, calinski=66.79375705838629),
'hdbscan': Metrics(silhouette=0.12551886836376325, davies=1.9489708574623812, calinski=27.39201136703522),
'kmeans': Metrics(silhouette=0.2378531239217623, davies=1.5285566112731594, calinski=86.09157814257729)}
print("Sorted by Calinski-Harabasz")
print("---------------------------")
print("\n".join([f"{idx}: {alg[0]} -> {alg[1].calinski}" for idx, alg in enumerate(sorted(metric_stats.items(), key=lambda k: k[1].calinski, reverse=True), 1)]))
Sorted by Calinski-Harabasz --------------------------- 1: kmeans -> 86.09157814257729 2: agglomerative_ward -> 72.21532753341644 3: dbscan_euclidean -> 66.79375705838629 4: dbscan_cosine -> 59.72216013322556 5: agglomerative_average_cosine -> 53.813409016452525 6: dbscan_canberra -> 43.64947485308241 7: agglomerative_complete_cosine -> 43.342180410474114 8: hdbscan -> 27.39201136703522
print("Sorted by Davies-Bouldin")
print("------------------------")
print("\n".join([f"{idx}: {alg[0]} -> {alg[1].davies}" for idx, alg in enumerate(sorted(metric_stats.items(), key=lambda k: k[1].davies), 1)]))
Sorted by Davies-Bouldin ------------------------ 1: dbscan_euclidean -> 0.8082913537210814 2: kmeans -> 1.5285566112731594 3: agglomerative_ward -> 1.6386724367395287 4: dbscan_cosine -> 1.7962841929950921 5: hdbscan -> 1.9489708574623812 6: agglomerative_average_cosine -> 2.0850910072225193 7: agglomerative_complete_cosine -> 2.339718960788736 8: dbscan_canberra -> 2.742753086381493
print("Sorted by Silhouette")
print("--------------------")
print("\n".join([f"{idx}: {alg[0]} -> {alg[1].silhouette}" for idx, alg in enumerate(sorted(metric_stats.items(), key=lambda k: k[1].silhouette, reverse=True), 1)]))
Sorted by Silhouette -------------------- 1: dbscan_euclidean -> 0.6129352430409912 2: kmeans -> 0.2378531239217623 3: agglomerative_ward -> 0.1740790530715999 4: agglomerative_complete_cosine -> 0.13931449234623647 5: hdbscan -> 0.12551886836376325 6: dbscan_cosine -> 0.08862792526465896 7: agglomerative_average_cosine -> 0.08797497634337614 8: dbscan_canberra -> 0.06696330466267836
dbscan_euclidean показывает хорошие результаты на метриках, но на практике кластеризация крайне далека от идеала, кидая почти всё в один кластер (ставлю дизлайк, в общем)kmeans и agglomerative_ward кластеризуют достаточно адекватно и примерно одинаковоdbscan_canberra отрабататывает достаточно плохоhdbscan по метрикам работает хуже, чем dbscan, но на практике показывает более адекватные результатыkmeans кластеризиет хорошо как по метрикам, так и на практике (отдам предпочтение ему)km = KMeans(n_clusters=3)
clusters = km.fit_predict(scaled_data.values)
plot_samples(data_embedded, clusters)
<AxesSubplot:>
data["Cluster"] = clusters
data.head()
| Place | Climate | HousingCost | HlthCare | Crime | Transp | Educ | Arts | Recreat | Econ | Long | Lat | Pop | Cluster | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | Abilene,TX | 521 | 6200 | 237 | 923 | 4031 | 2757 | 996 | 1405 | 7633 | -99.6890 | 32.5590 | 110932 | 1 |
| 1 | Akron,OH | 575 | 8138 | 1656 | 886 | 4883 | 2438 | 5564 | 2632 | 4350 | -81.5180 | 41.0850 | 660328 | 0 |
| 2 | Albany,GA | 468 | 7339 | 618 | 970 | 2531 | 2560 | 237 | 859 | 5250 | -84.1580 | 31.5750 | 112402 | 1 |
| 3 | Albany-Schenectady-Troy,NY | 476 | 7908 | 1431 | 610 | 6883 | 3399 | 4655 | 1617 | 5864 | -73.7983 | 42.7327 | 835880 | 0 |
| 4 | Albuquerque,NM | 659 | 8393 | 1853 | 1483 | 6558 | 3026 | 4496 | 2612 | 5727 | -106.6500 | 35.0830 | 419700 | 0 |
data["Cluster"].value_counts()
1 211 0 111 2 7 Name: Cluster, dtype: int64
data.drop(["Long", "Lat"], axis=1).groupby("Cluster").mean()
| Climate | HousingCost | HlthCare | Crime | Transp | Educ | Arts | Recreat | Econ | Pop | |
|---|---|---|---|---|---|---|---|---|---|---|
| Cluster | ||||||||||
| 0 | 588.288288 | 10029.945946 | 1724.540541 | 1126.153153 | 5096.729730 | 2950.693694 | 5048.045045 | 2446.036036 | 6068.675676 | 8.056767e+05 |
| 1 | 509.412322 | 7357.284360 | 762.810427 | 855.516588 | 3663.127962 | 2724.867299 | 1425.345972 | 1499.151659 | 5243.535545 | 2.145611e+05 |
| 2 | 636.714286 | 11472.428571 | 5390.142857 | 1524.285714 | 6637.142857 | 3374.857143 | 25080.000000 | 2784.142857 | 5405.142857 | 5.296353e+06 |
Выводы:
import plotly.graph_objects as go
import plotly.offline as py
fig = go.FigureWidget(data=go.Scattergeo(
lon = data['Long'],
lat = data['Lat'],
text = data['Place'],
mode = 'markers',
marker_color = data['Cluster'],
))
fig.update_layout(
title = 'US city clusters<br>(Hover for city-state names)',
geo_scope='usa',
width=1400,
height=700,
autosize=False
)
fig.show(renderer="jupyterlab")